package leetcode;

/*
563. 二叉树的坡度
给定一个二叉树，计算整个树的坡度。
一个树的节点的坡度定义即为，该节点左子树的结点之和和右子树结点之和的差的绝对值。空结点的的坡度是0。
整个树的坡度就是其所有节点的坡度之和。
示例：
输入：
         1
       /   \
      2     3
输出：1
解释：
结点 2 的坡度: 0
结点 3 的坡度: 0
结点 1 的坡度: |2-3| = 1
树的坡度 : 0 + 0 + 1 = 1
提示：
任何子树的结点的和不会超过 32 位整数的范围。
坡度的值不会超过 32 位整数的范围。
*/

public class problems_563 {
    public static void main(String[] args) {
        TreeNode A1 = new TreeNode(1);
        TreeNode A2 = new TreeNode(2);
        TreeNode A3 = new TreeNode(3);
        TreeNode A4 = new TreeNode(4);
        TreeNode A5 = new TreeNode(5);
//        TreeNode A6 = new TreeNode(6);
//        TreeNode A7 = new TreeNode(7);
        A1.left = A2;
        A1.right = A3;
        A2.left = A4;
//        A2.right = A5;
//        A3.left = A6;
//        A3.right = A7;
        A4.left = A5;
        System.out.println(new Solution().findTilt(A1));
    }

    static public class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode(int x) {
            val = x;
        }
    }

    static public class Solution {
        int tilt = 0;
        public int findTilt(TreeNode root) {
            traverse(root);
            return tilt;
        }
        public int traverse(TreeNode root) {
            if (root == null)
                return 0;
            int left = traverse(root.left);
            int right = traverse(root.right);
            tilt += Math.abs(left - right);
            return left + right + root.val;
        }
    }


//    static class Solution {
//        public int findTilt(TreeNode root) {
//            dfs(root);
//            return root.val;
//        }
//        private void dfs(TreeNode node){
//            if(null == node) return ;
//            if(null != node.left) dfs(node.left);
//            if(null != node.right) dfs(node.right);
//            if(null != node.left || null != node.right){
//                node.val = Math.abs(Math.subtractExact(null != node.left ? node.left.val : 0, null != node.right ? node.right.val : 0));
//            }
//        }
//    }
}